import java.util.Arrays;

/**
 * 75. 颜色分类
 */
public class Solution_75 {
    /**
     * 方法三：单指针
     */
    public void sortColors(int[] nums) {
        int len = nums.length;
        int ptr = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ptr++;
            }
        }
        for (int i = ptr; i < len; i++) {
            if (nums[i] == 1) {
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ptr++;
            }
        }
    }

    /**
     * 方法二：统计数组中 0，1，2 的数量，再重写数组
     */
    public void sortColors2(int[] nums) {
        int count0 = 0, count1 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count0++;
            }
            if (nums[i] == 1) {
                count1++;
            }
        }

        for (int j = 0; j < count0; j++) {
            nums[j] = 0;
        }
        for (int j = count0; j < count0 + count1; j++) {
            nums[j] = 1;
        }
        for (int j = count0 + count1; j < nums.length; j++) {
            nums[j] = 2;
        }
    }

    /**
     * 方法一：直接排序
     */
    public void sortColors1(int[] nums) {
        Arrays.sort(nums);
    }

    public static void main(String[] args) {
        Solution_75 solution = new Solution_75();
        int[] nums = { 2, 0, 2, 1, 1, 0 };
        solution.sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }
}
